Лемма о независимости

Пусть $\lambda_1, \ldots, \lambda_s$ — различные корни характеристического многочлена рекуррентного соотношения $f(n) = a_1 f(n - 1) + \ldots + a_k f(n - k)$. Тогда множество функций $\{\lambda_1^n, \ldots, \lambda_s^n\}$ линейно независимо.

Выпишем функции $\lambda_1^n, \ldots, \lambda_s^n$ как векторы их значений: $$ \begin{aligned} \lambda_1^n &= (1, \lambda_1, \ldots, \lambda_1^{s-1}, \lambda_1^s, \ldots) \\ \lambda_2^n &= (1, \lambda_2, \ldots, \lambda_2^{s-1}, \lambda_2^s, \ldots) \\ &\vdots \\ \lambda_s^n &= (1, \lambda_s, \ldots, \lambda_s^{s-1}, \lambda_s^s, \ldots) \end{aligned} $$ В первых $s$ столбцах видим матрицу Вандермонда, определитель которой равен 0 только если $\lambda_i = \lambda_j$ для некоторых $i \neq j$. В нашем случае, поскольку все корни различны, определитель $\neq 0$, а значит множество функций линейно независимо. $\square$